Although modeling systems in Mechanical Computer Aided Design and in animation are expanding their geometric domain to free form surfaces, polyhedral models remain the primary 3D representation used in the manufacturing, architectural, Geographic Information Systems, geoscience, and entertainment industries. Polyhedral models are particularly effective for hardware assisted rendering, which is important for video-games, virtual reality, fly-through, and electronic mock-up applications involving complex Computer Aided Design models.
In comparison to image and video compression, little attention has been devoted to the compression of 3D shapes, both from the research community and from 3D data exchange standards committees. This situation is likely to change rapidly for three reasons. 1) The exploding complexity of industrial Computer Aided Design models raises significantly the cost of the memory and auxiliary storage required by these models. 2) The distribution of 3D models over networks for collaborative design, gaming, rapid prototyping, or virtual interactions is seriously limited by the available bandwidth. 3) The graphics performance of high level hardware adapters is limited by insufficient on-board memory to store the entire model or by a data transfer bottleneck.
Since methods are known in the prior art for easily and efficiently triangulating arbitrary polygonal faces, it is sufficient to consider geometric models defined by triangular meshes. A triangular mesh is defined by the position of its vertices (geometry), which are n-dimensional vectors, by the association between each triangle and its sustaining vertices (connectivity), and by colors, normals, and texture coordinates (photometry), which does not affect the 3D geometry, but influences the way it is shaded.
The prior art in 3D geometric compression may be divided into three categories: simplification, geometry encoding, and connectivity encoding.
Polyhedral simplification techniques reduce the number of vertices in the mesh by altering the model's connectivity and by possibly adjusting the position of the remaining vertices to minimize the error produced by the simplification. These techniques target the generation of multiple levels of detail (LOD) for accelerated graphics or data reduction for over-sampled meshes. Although these techniques could be considered for lossy compression, they are inappropriate for applications that require access to the exact connectivity of the model. In fact simplification techniques are orthogonal to the compression techniques described here because geometric compression may be applied to each level of detail.
Geometry encoding techniques use lossy or lossless compression to reduce the storage necessary for the geometric data associated with vertex positions, and possibly with colors, normals and texture coordinates. Applying general purpose binary compression algorithms to the geometric data stream leads to suboptimal solutions. A geometric compression approach that involves normalizing the geometry into a unit cube and rounding off the vertex coordinates to fixed length integers is described by Michael Deering in "Geometric Compression", Computer Graphics (Proc. SIGGRAPH), pages 13-20, August 1995, which is here incorporated by reference in its entirety. The rounding controls the amount of lost information.
Connectivity encoding techniques attempt to reduce the redundancy inherent to many popular representations of polyhedral or triangular meshes. For example, Connectivity encoding techniques try to minimize the number of bits required to represent without loss of information the triangles of a triangular mesh of V vertices and T triangles.
On one extreme, if the vertices are always organized into a regular 2D grid, the triangle mesh may be completely defined by the number of rows and columns of the grid. Regular grids may be appropriate for terrain modeling in Geographic Information Systems and for rendering uniformly tesselated non-trimmed rectangular parametric patches. However, they are not suitable for modeling the more general 3D shapes found in Computer Aided Design, entertainment, and other applications.
At the other extreme, the vertex positions of a triangular mesh of V vertices and T triangles may be represented with an array, the vertex positions array, and each triangle may be represented by 3 indices into the vertex positions array. This solution does not impose any topological limitations on the mesh, but requires storing 3 addresses per triangle (approximately 6 addresses per vertex for typical triangular meshes). Even if the models were restricted to less than 1000 vertices, this scheme would consume 60 bits per vertex for the connectivity information alone.
Triangle strips used in graphics application programming interfaces (APIs) (described by J. Neider, T. Davis, and M. Woo. in OpenGL Programming Guide, Addison-Wesley, 1993; which is here incorporated by reference in its entirety) provide a compromise where a new vertex is combined with the previous two vertices to implicitly define a new triangle in the current strip. Triangle strips only pay off if one can build long strips, which is a challenging computational geometry problem. Furthermore, because on average a vertex is used twice, either as part of the same triangle strip or of two different ones, the use of triangle strips with OpenGL requires sending most vertices multiple times. The absence of the swap operation further increases this redundancy.
The application of triangle strips as a compression technique, where the locations of all vertices are available for random access during decompression, would still require storing one vertex reference per triangle, two vertex references per strip, the book keeping information on the number and length of the strips, and an additional bit of information per triangle indicating witch open side of the previous triangle should be used as the basis for the next triangle (this bit is equivalent to the SWAP operation in GL).
In Deering's method a stack-buffer is used to store 16 of the previously used vertices instead of having random access to all of the vertices of the model. This is a suitable solution for adapters with very limited on-board memory. Deering also generalizes the triangle strip syntax by providing more general control over how the next vertex is used and by allowing the temporary inclusion of the current vertex on the stack and the reuse of any one of the 16 vertices of the stack-buffer. The storage cost for this connectivity information is: one bit per vertex to indicate whether the vertex should be pushed onto the stack-buffer, two bits per triangle to indicate how to continue the current strip, one bit per triangle to indicate whether a new vertex should be read or whether a vertex from the stack-buffer should be used, and 4 bits of address for selecting a vertex from the stack-buffer, each time an old vertex is reused. Assuming that each vertex is reused only once, the total cost for encoding the connectivity information is: 1+4 bits per vertex plus 2+1 bits per triangle. Assuming 2 triangles per vertex, the total cost is roughly 11 bits per vertex. As far as we know, algorithms for systematically creating good traversals of general meshes using Deering's generalized triangle mesh syntax have not yet been developed. Naive traversal of the mesh may result in many isolated triangles or small runs, implying that a significant portion of the vertices will be sent more than once, and hence increasing the number of bits per triangle. None of the prior art methods for connectivity encoding preserve the original connectivity of the triangular mesh. All of these methods partition the triangular mesh into connected subsets of triangles. The vertices shared by two or more parts are represented multiple times. This may not be a problem when the compression method is meant to be used to better utilize the communication bandwidth between a CPU and a graphics adapter in a computer, but this change of connectivity is a serious disadvantage in other applications which require preserving the topological properties of the original mesh.
FIG. 1, comprising FIG. 1A and FIG. 1B, is a prior art example of trees. The prior art (described by "R. E. Tarjan." in Data Structures and Network Algorithms, SIAM, 1983; which is here incorporated by reference in its entirety) recognizes that a tree 1000 is composed of one or more nodes and one or more edges, each edge connecting a pair of the nodes. A node 1010 connected by a single edge 1015 to another node 1030 is a leaf node. A node 1020 connected by two edges (1025, 1035) to two other nodes (1030, 1050) is a regular node. A node 1030 connected by three or more edges (1015, 1035, 1045) to respective nodes (1010, 1020, and 1055) is a branching node. A tree can be described as a set of one or more runs. A run is a sequence of nodes, with each pair of consecutive nodes connected by an edge. The sequence has a first node that is a leaf or branching node, zero or more intermediate nodes that are regular nodes, and a last node that is a leaf or branching node. For example, the leaf node 1040, the regular nodes 1050 and 1020, and the branching node 1030 define the run (1040,1050,1020,1030).
A rooted tree 1100 is a tree with one of its nodes 1110 identified as a root node. The root node determines a parent-child relation between each pair of nodes connected by an edge. The root node also determines the first and last node of each run. The root node partially determines an order of traversal of the rooted tree. To fully specify the order of traversal, the runs must be further partitioned into one or more sets of common first node runs, each set composed of all the runs that share a common first node, and an ordering must be assigned to the runs within each one of the sets of common first node runs. For example, the choice of node 1110 as the root of the rooted tree 1100 determines that nodes 1120 and 1150 are the first and last nodes of run (1120,1130,1140,1150), respectively, and nodes 1120 and 1180 are the first and last nodes of run (1120,1160,1170,1180), respectively. But which one of these two runs is traversed first is not determined by the choice of node 1110 as the root of the tree, and has to be explicitly specified.
FIG. 2, comprising FIG. 2A, FIG. 2B, FIG. 2C, FIG. 2D, and FIG. 2E, is prior art example of triangular meshes. A triangular mesh 2100 is composed of vertices 2110, edges 2120, and triangles 2130.
A path on a triangular mesh is a sequence of non-repeated vertices such that each pair of consecutive vertices are connected by an edge. The first and last vertex of a path are said to be connected by the path. For example, the vertices 2140 and 2165 are connected by the path defined by the sequence formed by vertices 2140, 2150, 2160, and 2165. A triangular mesh is connected if every pair of its vertices is connected by a path. For example, the triangular mesh 2100 is connected, and the triangular mesh 2200 is not. When a triangular mesh is not connected it is composed of two or more connected components, where each connected component is a connected triangular mesh composed of a subset of vertices, edges, and triangles of the original triangular mesh and with two vertices of the triangular mesh belonging to the same connected component if they are connected by a path. For example, the triangular mesh 2200 is composed of two connected components, the triangular mesh 2210, and 2220. Vertices 2230 and 2240 belong to the same connected component because they can be connected by a path. Vertices 2230 and 2250 belong to different connected components because there exists no path connecting them.
An edge of a triangular mesh is a boundary edge if it belongs to exactly one triangle, an internal edge if is shared by exactly two triangles, and a singular edge if it is shared by three or more triangles. For example, edge 2350 of triangular mesh 2300 is a boundary edge, all the edges of triangular mesh 2100 are internal edges, and edge 2340, of the triangular mesh 2300 is a singular edge, because it is shared by triangles 2310, 2320, and 2330. (Note that boundary edges and internal edges are also called regular edges.) A vertex of a triangular mesh is a regular vertex if the set of vertices of all the triangles of the triangular mesh that contain the vertex, excluding the given vertex, can be reordered to define a single path. If a vertex is not a regular vertex, then it is a singular vertex. For example, all the vertices of triangular mesh 2100 are regular, and vertex 2410 of triangular mesh 2400 is singular because there is no way of reordering the vertices of all the triangles incident to vertex 2410, excluding vertex 2410, to form a single path. A triangular mesh has boundary if it has one or more boundary edges. For example, the triangular meshes 2100 and 2200 have no boundary, and the triangular meshes 2300 and 2400 have a boundary. A triangular mesh is a manifold if it has no singular vertices and no singular edges. If a triangular mesh is not a manifold, it is a non-manifold. For example, the triangular meshes 2100 and 2200 are manifolds, but the triangular mesh 2300 is a non-manifold.
An orientation of a triangle of a triangular mesh is an ordering of the tree vertices of the triangle, modulo cyclical permutations. Therefore, a triangle of a triangular mesh has two possible orientations. For example, the two different orientations of triangle 2130, composed of vertices 2110, 2170, and 2180, are the orderings (2110,2170,2180) and (2180,2170,2110). But the orderings (2110,2170,2180) and (2180,2110,2170) define the same orientation of the triangle because they are related by a cyclical permutation.
An orientation of an edge of a triangular mesh is one of the two possible orderings of the two vertices of the edge. For example, the two orientations of edge 2120 of the triangular mesh 2100 are defined by the orderings (2110,2170) and (2170,2110) of the vertices 2110 and 2170. The two orientations of an edge are said to be opposite of each other. An orientation of a triangle induces a consistent orientation on the three incident edges. For example, the orientation (2110,2170,2180) induces the consistent orientations (2110,2170), (2170,2180), and (2180,2110) on the three edges of triangle 2130. A manifold triangular mesh is orientable if an orientation can be chosen for each triangle of the triangular mesh in such a way that for each internal edge of the triangular mesh, the two triangles incident to the edge induce opposite orientations on the common edge. If a manifold triangular mesh is not orientable, then it is non-orientable All non-manifold triangular meshs are non-orientable. For example, triangular mesh 2100 is orientable, and triangular mesh 2500 is non-orientable.
The Euler characteristic of a triangular mesh with V vertices, E edges, and T triangles is the number X=V-E+F. It is known in the prior art (described by "W. S. Massey" in Algebraic Topology: An Introduction, Harcourt, Brace & World, 1967; which is here incorporated by reference in its entirety) that two connected manifold triangular meshes of the same Euler characteristic can be continuously deformed into one another if both are orientable, or both are non-orientable.
A triangular mesh with V vertices and T triangles is usually represented in the prior art (described by "Foley et.al." in Computer Graphics: Principles and Practice, Addison-Wesley, 1990; which is here incorporated by reference in its entirety) by a vertex positions array and a triangle array. The position of each vertex of the triangular mesh is represented in the vertex positions array by n floating point coordinates. Each triangle of the triangular mesh is represented in the triangle array by three indices to the vertex positions array.
For the purposes of this disclosure, a simple triangular mesh is a triangular mesh with n-dimensional vertices that is connected, oriented, manifold, without boundary, and of Euler characteristic 2. For example, triangular mesh 2100 is a simple triangular mesh in 3-dimensional space. For example, every simple triangular mesh can be obtained by triangulating and continuously deforming a sphere. If a triangular mesh is not simple, it is complex. Some examples of complex triangular meshes are shown in FIGS. 2B through 2E.